package test230529;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/5/29 0:13
 * 三步问题
 * https://leetcode.cn/problems/three-steps-problem-lcci/
 */
public class Solution02 {

    final int MOD = (int)1e9 + 7; // 取模常量

    public int waysToStep(int n) {
        // 边界处理
        if (n == 1 || n == 2) {
            return n;
        }
        if (n == 3) {
            return 4;
        }
        // 定义 ni 为到达 i 层台阶需要的总方式数
        int n1 = 1, n2 = 2, n3 = 4;
        for (int i = 4; i <= n; i++) {
            int curN = ((n1 + n2) % MOD + n3) % MOD;
            n1 = n2;
            n2 = n3;
            n3 = curN;
        }
        return n3;
    }
}
